Graph Interpolation Grammars are a declarative formalism with an operationalsemantics. Their goal is to emulate salient features of the human parser, andnotably incrementality. The parsing process defined by GIGs incrementallybuilds a syntactic representation of a sentence as each successive lexeme isread. A GIG rule specifies a set of parse configurations that trigger itsapplication and an operation to perform on a matching configuration. Rules arepartly context-sensitive; furthermore, they are reversible, meaning that theiroperations can be undone, which allows the parsing process to benondeterministic. These two factors confer enough expressive power to theformalism for parsing natural languages.
展开▼